import json
import random

def generate_test_cases():
    """生成超级幂算法的测试用例"""
    test_cases = []
    
    # 基础测试用例
    basic_cases = [
        # 简单情况
        (2, [3], "2^3 = 8"),
        (2, [1, 0], "2^10 = 1024"),
        (1, [4, 3, 3, 8, 5, 2], "1的任意次幂都是1"),
        (2, [1], "2^1 = 2"),
        (3, [2], "3^2 = 9"),
        (4, [1], "4^1 = 4"),
        (5, [0], "5^0 = 1"),
        
        # 边界情况
        (0, [1], "0^1 = 0"),
        (10, [1], "10^1 = 10"),
        (100, [1], "100^1 = 100"),
        
        # 大数情况
        (2, [1, 4, 7, 4, 8, 3, 6, 4, 7], "大指数测试"),
        (123, [4, 5, 6], "123^456"),
        (999, [1, 0, 0, 0], "999^1000"),
        
        # 特殊值
        (1337, [1], "1337^1 = 0 (mod 1337)"),
        (1338, [1], "1338^1 = 1 (mod 1337)"),
        (2674, [1], "2674^1 = 0 (mod 1337)"),
    ]
    
    for a, b, desc in basic_cases:
        # 计算期望结果（用于验证）
        expected = calculate_expected(a, b)
        
        test_cases.append({
            "input_a": a,
            "input_b": b,
            "expected": expected,
            "description": desc
        })
    
    # 边界值测试
    edge_cases = [
        # 最小值
        (1, [0], "最小指数0"),
        (1, [1], "底数和指数都是1"),
        
        # 模数边界
        (1336, [1], "接近模数1337"),
        (1337, [2], "等于模数1337"),
        (1338, [2], "超过模数1337"),
        
        # 长指数
        (2, [1] * 20, "长指数数组"),
        (2, [9] * 10, "最大单位数字"),
        
        # 零的情况
        (0, [5], "0的正次幂"),
        (0, [1, 0, 0], "0的大正次幂"),
    ]
    
    for a, b, desc in edge_cases:
        expected = calculate_expected(a, b)
        
        test_cases.append({
            "input_a": a,
            "input_b": b,
            "expected": expected,
            "description": desc
        })
    
    # 随机生成测试用例
    random.seed(42)  # 设置随机种子确保可重复性
    
    for i in range(30):
        # 生成随机底数
        a = random.randint(0, 10000)
        
        # 生成随机指数（数组长度1-10）
        b_length = random.randint(1, 10)
        b = [random.randint(0, 9) for _ in range(b_length)]
        
        # 确保不是全零（除了单个0）
        if b_length > 1 and all(digit == 0 for digit in b):
            b[0] = random.randint(1, 9)
        
        expected = calculate_expected(a, b)
        
        test_cases.append({
            "input_a": a,
            "input_b": b,
            "expected": expected,
            "description": f"随机用例{i+1}: {a}^{''.join(map(str, b))}"
        })
    
    # 性能测试用例
    performance_cases = [
        (2, [1] * 100, "性能测试: 长指数1"),
        (1000, [9] * 50, "性能测试: 大底数长指数"),
        (12345, [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] * 5, "性能测试: 超长指数"),
        (99999, [8, 7, 6, 5, 4, 3, 2, 1], "性能测试: 大底数"),
    ]
    
    for a, b, desc in performance_cases:
        expected = calculate_expected(a, b)
        
        test_cases.append({
            "input_a": a,
            "input_b": b,
            "expected": expected,
            "description": desc,
            "is_performance_test": True
        })
    
    return test_cases

def calculate_expected(a, b):
    """计算期望结果（使用正确的算法）"""
    MOD = 1337
    
    def power_mod(base, exp, mod):
        """计算 base^exp % mod"""
        if exp == 0:
            return 1
        result = 1
        base = base % mod
        while exp > 0:
            if exp % 2 == 1:
                result = (result * base) % mod
            exp = exp >> 1
            base = (base * base) % mod
        return result
    
    # 将数组转换为整数
    if not b:
        return 1
    
    b_int = 0
    for digit in b:
        b_int = b_int * 10 + digit
    
    # 由于指数可能非常大，我们需要使用欧拉定理
    # a^φ(m) ≡ 1 (mod m) 当 gcd(a,m) = 1
    # 1337 = 7 × 191，φ(1337) = 6 × 190 = 1140
    
    if b_int == 0:
        return 1
    
    # 使用欧拉定理优化
    phi_1337 = 1140  # φ(1337) = 1140
    
    if gcd(a, 1337) == 1:
        # 当a与1337互质时，使用欧拉定理
        exp_mod = b_int % phi_1337
        if exp_mod == 0 and b_int > 0:
            exp_mod = phi_1337
        return power_mod(a, exp_mod, MOD)
    else:
        # 当a与1337不互质时，直接计算（需要特殊处理）
        return power_mod(a, b_int, MOD)

def gcd(a, b):
    """计算最大公约数"""
    while b:
        a, b = b, a % b
    return a

def save_test_cases(filename="super_pow_test_cases.json"):
    """保存测试用例到文件"""
    test_cases = generate_test_cases()
    
    # 添加统计信息
    performance_count = sum(1 for case in test_cases if case.get("is_performance_test", False))
    max_b_length = max(len(case["input_b"]) for case in test_cases)
    
    data = {
        "test_cases": test_cases,
        "statistics": {
            "total_test_cases": len(test_cases),
            "performance_test_cases": performance_count,
            "max_exponent_length": max_b_length,
            "modulus": 1337
        }
    }
    
    with open(filename, 'w', encoding='utf-8') as f:
        json.dump(data, f, ensure_ascii=False, indent=2)
    
    print(f"已生成 {len(test_cases)} 个测试用例")
    print(f"性能测试用例: {performance_count}")
    print(f"最大指数长度: {max_b_length}")
    print(f"保存到: {filename}")
    
    return data

def preview_test_cases():
    """预览测试用例"""
    test_cases = generate_test_cases()
    
    print("=== 超级幂测试用例预览 ===")
    print(f"总测试用例数: {len(test_cases)}")
    print("\n前15个测试用例:")
    print("-" * 80)
    
    for i, case in enumerate(test_cases[:15]):
        b_str = ''.join(map(str, case['input_b']))
        print(f"{i+1:2d}. {case['description']}")
        print(f"    输入: a={case['input_a']}, b=[{','.join(map(str, case['input_b']))}]")
        print(f"    即: {case['input_a']}^{b_str}")
        print(f"    期望结果: {case['expected']}")
        print()

if __name__ == "__main__":
    # 预览测试用例
    preview_test_cases()
    
    # 生成并保存测试用例
    data = save_test_cases()
    
    # 显示统计信息
    stats = data["statistics"]
    print(f"\n=== 统计信息 ===")
    print(f"总测试用例数: {stats['total_test_cases']}")
    print(f"性能测试用例: {stats['performance_test_cases']}")
    print(f"最大指数长度: {stats['max_exponent_length']}")
    print(f"模数: {stats['modulus']}")
